package com.example.algorithm.backtracing;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
 * perm[i] 能够被 i 整除
 * i 能够被 perm[i] 整除
 * 给你一个整数 n ，返回可以构造的 优美排列 的 数量 。
 * <p>
 * 示例 1：
 * 输入：n = 2
 * 输出：2
 * 解释：
 * 第 1 个优美的排列是 [1,2]：
 * - perm[1] = 1 能被 i = 1 整除
 * - perm[2] = 2 能被 i = 2 整除
 * 第 2 个优美的排列是 [2,1]:
 * - perm[1] = 2 能被 i = 1 整除
 * - i = 2 能被 perm[2] = 1 整除
 * <p>
 * 示例 2：
 * 输入：n = 1
 * 输出：1
 */
public class Leetcode526_CountArrangement {

    static class Solution {
        /**
         * 状态压缩 + 动态规划
         * 若 mask 中的第 i 位为 1（从 0 开始编号），则数 i+1 已经被选取，否则就还未被选取
         * 以 n = 4, n=4,mask=(0110)2为例，这代表数 2,3 都已经被选取并以任意顺序放置在排列中前两个位置
         *
         * @param n
         * @return
         */
        private int countArrangement2(int n) {
            int[] dp = new int[1 << n];
            dp[0] = 1;
            for (int mask = 1; mask < (1 << n); mask++) {
                int num = Integer.bitCount(mask);
                for (int i = 0; i < n; i++) {
                    if ((mask & (1 << i)) != 0
                            && ((num % (i + 1)) == 0 || (i + 1) % num == 0))
                        dp[mask] += dp[mask ^ (1 << i)];
                }
            }
            return dp[(1 << n) - 1];
        }

        /**
         * 回溯法
         * 先预处理每个位置的符合条件的数有哪些
         * 然后尝试向位置 index 放入符合条件的数
         * 最后能将 1~n 全部排列的，那么优美排列结果数 + 1
         *
         * @param n
         * @return
         */
        int res = 0;
        List<Integer>[] match;

        private int countArrangement1(int n) {
            match = new List[n + 1];
            for (int i = 0; i <= n; i++)
                match[i] = new ArrayList();
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++) {
                    if (i % j == 0 || j % i == 0) match[i].add(j);
                }
            backTrack(1, n, new HashSet<>());
            return res;
        }

        private void backTrack(int index, int n, Set<Integer> visited) {
            if (index == n + 1) {
                res++;
                return;
            }
            for (Integer num : match[index]) {
                if (!visited.contains(num)) {
                    visited.add(num);
                    backTrack(index + 1, n, visited);
                    visited.remove(num);
                }
            }
        }

        public int countArrangement(int n) {
            return countArrangement2(n);
        }
    }

    public static void main(String[] args) {
        int n = 2;
        n = 11;
        System.out.println(new Solution().countArrangement(n));
    }
}
